// Simple LRU cache use doubly linked list

/**
 * Simple double linked list. Compared with array, it has O(1) remove operation.
 * @constructor
 */
var LinkedList = function () {
  /**
   * @property {LRU~Entry}
   */
  this.head = null;

  /**
   * @property {LRU~Entry}
   */
  this.tail = null;

  this._len = 0;
};

var linkedListProto = LinkedList.prototype;
/**
 * Insert a new value at the tail
 * @param  {} val
 * @return {LRU~Entry}
 */
linkedListProto.insert = function (val) {
  var entry = new Entry(val);
  this.insertEntry(entry);
  return entry;
};

/**
 * Insert an entry at the tail
 * @param  {LRU~Entry} entry
 */
linkedListProto.insertEntry = function (entry) {
  if (!this.head) {
    this.head = this.tail = entry;
  } else {
    this.tail.next = entry;
    entry.prev = this.tail;
    entry.next = null;
    this.tail = entry;
  }
  this._len++;
};

/**
 * Remove entry.
 * @param  {LRU~Entry} entry
 */
linkedListProto.remove = function (entry) {
  var prev = entry.prev;
  var next = entry.next;
  if (prev) {
    prev.next = next;
  } else {
    // Is head
    this.head = next;
  }
  if (next) {
    next.prev = prev;
  } else {
    // Is tail
    this.tail = prev;
  }
  entry.next = entry.prev = null;
  this._len--;
};

/**
 * @return {Number}
 */
linkedListProto.len = function () {
  return this._len;
};

/**
 * Clear list
 */
linkedListProto.clear = function () {
  this.head = this.tail = null;
  this._len = 0;
};

/**
 * @constructor
 * @param {} val
 */
var Entry = function (val) {
  /**
   * @property {}
   */
  this.value = val;

  /**
   * @property {LRU~Entry}
   */
  this.next;

  /**
   * @property {LRU~Entry}
   */
  this.prev;
};

/**
 * LRU Cache
 * @constructor
 * @alias LRU
 */
var LRU = function (maxSize) {
  this._list = new LinkedList();

  this._map = {};

  this._maxSize = maxSize || 10;

  this._lastRemovedEntry = null;
};

var LRUProto = LRU.prototype;

/**
 * @param  {String} key
 * @param  {} value
 * @return {} Removed value
 */
LRUProto.put = function (key, value) {
  var list = this._list;
  var map = this._map;
  var removed = null;
  if (map[key] == null) {
    var len = list.len();
    // Reuse last removed entry
    var entry = this._lastRemovedEntry;

    if (len >= this._maxSize && len > 0) {
      // Remove the least recently used
      var leastUsedEntry = list.head;
      list.remove(leastUsedEntry);
      delete map[leastUsedEntry.key];

      removed = leastUsedEntry.value;
      this._lastRemovedEntry = leastUsedEntry;
    }

    if (entry) {
      entry.value = value;
    } else {
      entry = new Entry(value);
    }
    entry.key = key;
    list.insertEntry(entry);
    map[key] = entry;
  }

  return removed;
};

/**
 * @param  {String} key
 * @return {}
 */
LRUProto.get = function (key) {
  var entry = this._map[key];
  var list = this._list;
  if (entry != null) {
    // Put the latest used entry in the tail
    if (entry !== list.tail) {
      list.remove(entry);
      list.insertEntry(entry);
    }

    return entry.value;
  }
};

/**
 * Clear the cache
 */
LRUProto.clear = function () {
  this._list.clear();
  this._map = {};
};

export default LRU;
